Національний університет “Львівська політехніка” Інститут комп’ютерних наук і технологій Кафедра АСУ
Лабораторна робота №2 з курсу „Логічне програмування” Тема: «Спискові структури» Виконав: студент групи ІУС-51 Перевірив: Львів-2006 Мета роботи: Засвоїти основні поняття для роботи зі списками. Теоретичні відомості Список – це впорядкована множина елементів X1,X2,...XN, з якою можна оперувати як з однією змінною, наприклад: X = [X1,X2,X3,X4]. Для вирішення логічних задач можна складати рівняння над списками. Тоді, крім операції прирівнювання (“=“), яка означає, що всі елементи одного списку повинні співпадати з усіма елементами другого списку, вводиться операція відокремлення елементів списку – “|”. За допомогою операцій прирівнювання та відокремлення можна виразити будь-яке перетворення спискової структури. Наприклад, рівняння X=[Y|Z] означає, що першим елементом в списку X є елементарний елемент Y, а Z – це всі решта елементів списку. З рівняння [Y1|Z1] = [Y|Z] виходить, що Y1=Y, і Z1=Z. Звичайно, що Y повинно бути одним з простих типів (наприклад: integer, real, char, string, symbol), а Z – списком того самого типу (integer*, real*, char*, string*, symbol*). Відокремлювати можна декілька елементів, наприклад: X=[Y,P|L]. Якщо до виконання цього предикату прирівнювання деякі з елементів списку, або деякі змінні були невідомі (не зв'язаними), то після виконання прирівнювань невідомі значення стають відомими (зв'язаними), якщо вони прирівнювалися до відомих змінних. Таким чином, вбудований предикат “=“ може бути істинним лише тоді, коли вдалося прирівняти всі підсписки в списковому рівнянні. Відомі змінні можна лише порівнювати, тоді істинність предикату буде залежати від результату порівняння. Як вже говорилося, в логічній моделі кома між предикатами завжди означає зв'язку “і”, а повторення правил з однаковими головами означає логічне “або” між правими його частинами. В деяких випадках зручно використовувати як “або” символ “;”, але не слід цим зловживати, тому що програма не є наглядною, наприклад: I_want_buy(Car_model,Price,Color):-not(Color=“blue”);not(Color=“white”) – є тавтологією, тому що колір завжди або не синій, або не білий. Нижче подана проста демонстраційна програма для визначення невідомого чотирьохзначного числа. В ній до Вашого розгляду запропоновано один стандартний прийом вирішення логічних задач. Він полягає у висуванні пропозиції і перевірці, чи підійде вона для розв'язку задачі (дивіться предикат response у програмі). Для цієї перевірки використовується стандартна функція not, вживання якої засновано на класичному зв'язку кванторів “існує” та “всі”. Отже, “не існує об'єкту X” означає що “всі об'єкти не X”. В даній програмі взаємоперетворення кванторів здійснено у предикаті not(bad_check(Code)), що означає “не існує bad_check”. Завдяки тому відбувається неявний перебір всіх можливих рішень bad_check, які базуються на базі даних “history”. Domains /* задаємо тип “список цілих чисел” */ cod=integer* Predicates /* визначаємо типи предикатів */ propose(cod) choice(integer,cod) response(cod) bad_check(cod) check1(cod,cod,integer) read(integer) go(integer) Database /* визначаємо базу даних запитів та відповідей, яка поповнюється в процесі вирішення задачі */ history(cod, integer) Clauses /* логічна модель задачі: */ /* вибір числа X зі списку */ choice(X,[X|_]). /*означає, що за X можна прийняти перший елемент, підкреслення означає будь-яке значення*/ choice(X,[_|L]):-choice(X,L). /* або X вибрати з решти елементів L. */ /* Пропозиція загаданого коду - це список з чотирьох довільних цифр */ propose(Code):-choice(X1,[0,1,2,3...